/**
 * 给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


// 自己的写法
var maxDepth = function (root) {
    return findDep(root)
};

const findDep = (node, depth = 0) => {
    if (!node) return depth
    depth++
    const leftMax = findDep(node.left, depth)
    const rightMax = findDep(node.right, depth)
    return Math.max(leftMax, rightMax)
}

//另外一种
var maxDepth = function (root) {

    if (!root) return 0

    const left = maxDepth(root.left)
    const right = maxDepth(root.right)

    return Math.max(left, right) + 1
};
/**
 * bfs
 * 思路：层序遍历二叉树，每层结束的时候depth加1.
复杂度分析：时间复杂度O(n)，n 为二叉树的节点个数，每个节点只会被访问一次。空间复杂度O(n),表示队列中存放的元素，最坏情况下和二叉树节点个数一样

作者：chen-wei-f
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/solution/104-er-cha-shu-de-zui-da-shen-du-by-chen-emzv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @param {*} root 
 * @returns 
 */
const maxDepth = (root) => {
    if (root == null) return 0;
    const queue = [root];
    let depth = 1;
    while (queue.length) {
        // 当前层的节点个数
        const levelSize = queue.length;
        // 逐个让当前层的节点出列
        for (let i = 0; i < levelSize; i++) {
            // 当前出列的节点
            const cur = queue.shift();
            // 左右子节点入列
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
        }
        // 当前层所有节点已经出列，如果队列不为空，说明有下一层节点，depth+1
        if (queue.length) depth++;
    }
    return depth;
};
